#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>
#include <limits.h>
#include "tree.h"

using namespace std;

class preOrderIterator1
{
public:
    preOrderIterator1(Tree *root):cur(root) 
    {
	cur = root;
	myStack.push(NULL);
    }

    bool hasNext() { return !myStack.empty(); }

    int next() 
    {
	Tree *node = cur;
	if (node->right) myStack.push(node->right);
	if (cur->left) cur = cur->left;
	else {cur = myStack.top(); myStack.pop();}
	return node->data;
    }

private:
    stack<Tree *> myStack;
    Tree *cur;
};
//better method of preOrderIterator
class preOrderIterator
{
public:
    preOrderIterator(Tree *root):cur(root) 
    {
	if (root!= NULL) myStack.push(root);
    }

    bool hasNext() { return !myStack.empty(); }

    int next() 
    {
	Tree *node = myStack.top();
	myStack.pop();
	if (node->right) myStack.push(node->right);
	if (node->left) myStack.push(node->left);
	return node->data;
    }

private:
    stack<Tree *> myStack;
    Tree *cur;
};

class inOrderIterator
{
public:
    inOrderIterator(Tree *root):cur(root) 
    {
	while(root) {
	    myStack.push(root);
	    root = root->left;
	}
    }

    bool hasNext() { return !myStack.empty();}

    int next() 
    {
	Tree *top = myStack.top();
	myStack.pop();
	cur = top->right;
	while(cur) {
	    myStack.push(cur);
	    cur = cur->left;
	}
	return top->data;
    }

private:
    stack<Tree *> myStack;
    Tree *cur;
};

class postOrderIterator
{
public:
    postOrderIterator(Tree *root):cur(root) 
    {
	while(root) {
	    if (root->right) myStack.push(root->right);
	    myStack.push(root); 
	    root = root->left;
	}
    }

    bool hasNext() { return !myStack.empty(); }

    int next() 
    {
	Tree *node = myStack.top();
	myStack.pop();
	cout << "---->" << node->data << endl;
	Tree *root = myStack.top();
	cout << "---->" << root->data << endl;
	root = root->right;
	while(root) {
	    if (root->right) myStack.push(root->right);
	    myStack.push(root); 
	    root = root->left;
	}
	return node->data;
    }

private:
    stack<Tree *> myStack;
    Tree *cur;
};

int main(int argc, char **argv)
{
    int input[] = {21,7,5,6,3,2,1,4,6,23,43,54,12,54,8,10,11,35,56};
    //int input[] = {7};
    Tree *root = NULL, *root2 = NULL;
    vector<int> preOrder;
    int result;

    for (int i = 0; i < sizeof(input)/sizeof(int); i++) {
        TreeInsert(root, input[i]);
    }
    print_ascii_tree(root);

    inOrderIterator inIter(root);
    while(inIter.hasNext()) {
	cout << inIter.next() << " ";
    }
    cout << endl;

/*    preOrderIterator preIter(root);
    while(preIter.hasNext()) {
	cout << preIter.next() << " ";
    }
    cout << endl;

    postOrderIterator postIter(root);
    while(postIter.hasNext()) {
	cout << postIter.next() << " ";
	getchar();
    }
    cout << endl; */
}
